/**
 * 102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

 

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

 */

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder1 = function (root) {

    // //使用深度遍历
    // const dfe =(root,index)=>{
    //     if(!root) return
    //     res.push({val:root.val,index})
    //     dfe(root.left,index+1)
    //     dfe(root.right,index+1)
    // }
    // dfe(root,0)

    // let result = []
    // for(v of res){
    //     if(!result[v.index]){
    //        result[v.index]=[]
    //     }
    //     result[v.index].push(v.val)
    // }

    //--------优化版 少一层循环----------
    let result = []
    const dfe = (root, index) => {
        if (!root) return
        // res.push({val:root.val,index})
        result[index] ? result[index].push(root.val) : result[index] = [root.val]
        dfe(root.left, index + 1)
        dfe(root.right, index + 1)
    }
    dfe(root, 0)

    return result
};


var levelOrder = function (root) {
    //使用广序优先遍历、加队列先进先出的特性
    let res = []

    if (!root) {
        return res
    }

    let stack = [root]
    while (stack.length > 0) {
        const currentLength = stack.length;
        //每一层循环加一层数组
        res.push([])
        // 当前层遍历完
        for (var i = 0; i < currentLength; i++) {
            let node = stack.shift()
            res[res.length - 1].push(node.val)
            node.left && stack.push(node.left)
            node.right && stack.push(node.right)
        }
    }
    return res
}